package q438;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 438.找到字符串中所有字母异位词
 */
public class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        Map<Character, Integer> map = new HashMap<>();

        // 保存p字符串信息
        for (int i = 0; i < p.length(); i++) {
            char c = p.charAt(i);
            if (map.containsKey(c)) {
                map.put(c, map.get(c) + 1);
            } else {
                map.put(c, 1);
            }
        }

        // 结果
        List<Integer> result = new ArrayList<>();

        Map<Character, Integer> working = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);

            if (working.containsKey(c)) {
                working.put(c, working.get(c) + 1);
            } else {
                working.put(c, 1);
            }

            // 判断是否找到了异位词
            if (map.equals(working)) {
                result.add(i - p.length() + 1);
            }

            if (i >= p.length() - 1) {
                Character cc = s.charAt(i - p.length() + 1);
                if (working.get(cc) - 1 ==0) {
                    working.remove(cc);
                } else {
                    working.put(cc, working.get(cc) - 1);
                }
            }
        }


        return result;
    }

    public static void main(String[] args) {
        String s = "abacbabc";
//        String s = "cbaebabacd";
        String p = "abc";

        Solution solution = new Solution();
        List<Integer> anagrams = solution.findAnagrams(s, p);
        System.out.println(anagrams);
    }
}
